package demo.DataStrucAndAlgo.Stack;

import java.util.Scanner;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/24-07-24-9:24
 * @Description：demo.DataStrucAndAlgo.Stack   栈的运用--普通计算器和逆波兰计算器
 *
 **/
/*
栈结构，选取上面实现的链表模拟栈；在原有基础上，新增 isEmpty，getTop(获取栈顶)，priority（获取操作符的优先级），
isOper（判断是否为运算符），cal（输入两个数字与一个运算符进行数学运算）方法，具体实现见代码；
创建numStick用于存储数字，创建operStick用于存储运算符，对字符串进行逐项扫描，
每扫描一个字符判断其是否为运算符（+*-/)*/
/*是运算符时，就判断operStick空吗（isEmpty实现）？空就直接入栈，不空就要进行当前运算符与栈顶运算符（用getTop获取）进行优先级的比较（priority实现）
当前<=top，则将numStick中的两个栈点进行出栈，将operStick的栈顶进行出栈，这些出栈数据统统装入cal方法进行运算，运算结果放入numStick中，当前运算符入栈。当前>top，当前运算符直接入栈

不是运算符时，就直接入numStick栈；在上述判断执行完后，继续循环执行，直到字符串中所有字符都被扫描即可；
 扫描完成后，所有数据被列入栈中，上述操作的目的旨在将高级运算在入栈时，运算干净，这样栈里都是同级的运算
下面对栈中的同级运算数据进行运算，运算过程就是numStick出两个，operStick出一个，进入cal方法中运算，结果继续入numStick栈，然后接着重复计算，直到operStack中没有运算符残留，就结束。
 */
class DoubleLinkedStack{
    private DoubleNode root = new DoubleNode(0);
    public DoubleNode getRoot(){
        return this.root;
    }
    public void push(int data){  //普通add：不按序号存储
        DoubleNode temp = root;
        while(temp.next != null){
            temp = temp.next;
        }
        DoubleNode node = new DoubleNode(data);
        temp.next = node;
        node.pre = temp;
    }
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("空栈");
        }
        DoubleNode temp = root;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.pre.next = null;
        return temp.data;
    }
    public void show(){        //逆向打印
        if(isEmpty()){
            System.out.println("空栈");
            return;
        }
        DoubleNode temp = root;
        while(temp.next != null){
            temp = temp.next;
        }
        while(temp != root){
            System.out.println(temp);
            temp = temp.pre;
        }
    }
    public boolean isEmpty(){      //判断栈空
        return root.next == null;
    }
    public int getTop(){           //返回栈顶的值
        if(isEmpty()){
            throw new RuntimeException("空栈");
        }
        DoubleNode temp = root;
        while(temp.next != null){
            temp = temp.next;
        }
        return temp.data;
    }
    public int prioprity(int oper){        //返回运算符优先级，正比
        if(oper == '*' || oper == '/'){
            return 1;
        }else if(oper == '+' || oper == '-'){
            return 0;
        }else{
            return 1;
        }
    }
    public boolean isOper(int oper){   //判断是否为加减乘除
        return oper == '+' || oper == '-' || oper == '*' || oper == '/';
    }
    public int cal(int num1,int num2,int oper){
        int result = 0;
        switch (oper){
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num2 - num1;
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                result = num2 / num1;
                break;
        }
        return result;
    }
}
public class Stack_Calcu {
    public static void main(String[] args) {
        DoubleLinkedStack numStack = new DoubleLinkedStack();  //数字栈
        DoubleLinkedStack operStack = new DoubleLinkedStack(); //运算符栈
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();   //
        int index=0;    //对str进行扫描的索引
        char ch = ' ';     //保存每次扫描到的字符
        int num1;        //存储要计算的数字
        int num2;
        int value;        //用于承接临时计算数据
        //对字符串进行扫描，将所有数据录入栈中
        String number = "";
        while (true){
            ch=str.substring(index,index+1).charAt(0);
            if (operStack.isOper(ch) || ch == '(' || ch == ')'){//判断是否为操作符
                if (operStack.isEmpty()){//操作符栈空时，扫描到的操作符直接入栈
                    operStack.push(ch);
                }else if(ch == '('){
                    operStack.push(ch);
                }else if(operStack.getTop() == '('){
                    operStack.push(ch);
                }else if(ch == ')'){
                    int a;
                    operStack.show();
                    numStack.show();
                    while((a = operStack.pop())!='('){
                        num1=numStack.pop();
                        num2=numStack.pop();
                        value=operStack.cal(num1,num2,a);
                        numStack.push(value);
                    }
                }else if (operStack.prioprity(ch)<=operStack.prioprity(operStack.getTop())){//判断当前操作符的优先级<=栈顶操作符的优先级
                    num1=numStack.pop();
                    num2=numStack.pop();
                    value=operStack.cal(num1,num2,operStack.pop());
                    numStack.push(value);
                    operStack.push(ch);
                }else{//当前操作符的优先级>栈顶操作符的优先级
                    operStack.push(ch);
                }
            }else {
                //numStack.push(ch-'0');//数字是按char接收的，所以要减去'0'，从char恢复到int
                number = number+ch;     //合并所有扫描到的数字
                if(index == str.length()-1){     //如果为最后一个数字
                    numStack.push(Integer.parseInt(number));
                } else if(!(str.substring(index+1,index+2).charAt(0)<='9'&&str.substring(index+1,index+2).charAt(0)>='0')){   //判断下一个字符是否是数字，不是则入栈
                    numStack.push(Integer.parseInt(number));
                    number = "";
                }
            }
            index++;
            if (index==str.length()){//此时字符串中所有数据被扫描完
                break;
            }
        }
        numStack.show();
        System.out.println("---------");
        operStack.show();
        //对栈中数据进行计算
        while (true){
            if (operStack.isEmpty()){//当操作符栈空，数据计算完成
                break;
            }
            num1=numStack.pop();
            num2=numStack.pop();
            value=operStack.cal(num1,num2,operStack.pop());
            numStack.push(value);
        }
        System.out.printf("%s=%d",str,numStack.pop());
    }
}
